package twobranchsearch.lowescommon;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/13
 * @author 王光浩
 * @Thinking 使用迭代的方式（不同于普通的二叉树，在普通二叉树中使用迭代比较麻烦，因为需要返回值）
 * @Analsysis 时间复杂度O（n），空间复杂度O（1）
 */
public class MyMethodTwo {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		while(true) {
			if(root.val<p.val && root.val<q.val)root=root.right;
			else if(root.val>p.val && root.val>q.val)root=root.left;
			else return root;
		}
	}
}
